πŸ‘©β€πŸ’» 67257. μˆ˜μ‹ μ΅œλŒ€ν™”

@Seongukbaek Posted April 28, 2022 Β· Updated April 28, 2022 Β· 8 min read

문제

IT 벀처 νšŒμ‚¬λ₯Ό μš΄μ˜ν•˜κ³  μžˆλŠ” 라이언은 λ§€λ…„ 사내 해컀톀 λŒ€νšŒλ₯Ό κ°œμ΅œν•˜μ—¬ μš°μŠΉμžμ—κ²Œ μƒκΈˆμ„ μ§€κΈ‰ν•˜κ³  μžˆμŠ΅λ‹ˆλ‹€. 이번 λŒ€νšŒμ—μ„œλŠ” μš°μŠΉμžμ—κ²Œ μ§€κΈ‰λ˜λŠ” μƒκΈˆμ„ 이전 λŒ€νšŒμ™€λŠ” λ‹€λ₯΄κ²Œ λ‹€μŒκ³Ό 같은 λ°©μ‹μœΌλ‘œ κ²°μ •ν•˜λ €κ³  ν•©λ‹ˆλ‹€. 해컀톀 λŒ€νšŒμ— μ°Έκ°€ν•˜λŠ” λͺ¨λ“  μ°Έκ°€μžλ“€μ—κ²ŒλŠ” μˆ«μžλ“€κ³Ό 3κ°€μ§€μ˜ μ—°μ‚°λ¬Έμž(+, -, ) 만으둜 이루어진 μ—°μ‚° μˆ˜μ‹μ΄ μ „λ‹¬λ˜λ©°, μ°Έκ°€μžμ˜ λ―Έμ…˜μ€ 전달받은 μˆ˜μ‹μ— ν¬ν•¨λœ μ—°μ‚°μžμ˜ μš°μ„ μˆœμœ„λ₯Ό 자유둭게 μž¬μ •μ˜ν•˜μ—¬ λ§Œλ“€ 수 μžˆλŠ” κ°€μž₯ 큰 숫자λ₯Ό μ œμΆœν•˜λŠ” κ²ƒμž…λ‹ˆλ‹€. 단, μ—°μ‚°μžμ˜ μš°μ„ μˆœμœ„λ₯Ό μƒˆλ‘œ μ •μ˜ν•  λ•Œ, 같은 μˆœμœ„μ˜ μ—°μ‚°μžλŠ” μ—†μ–΄μ•Ό ν•©λ‹ˆλ‹€. 즉, + > - > * λ˜λŠ” - > * > + λ“±κ³Ό 같이 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •μ˜ν•  수 μžˆμœΌλ‚˜ +, > - λ˜λŠ” * > +,-처럼 2개 μ΄μƒμ˜ μ—°μ‚°μžκ°€ λ™μΌν•œ μˆœμœ„λ₯Ό 가지도둝 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •μ˜ν•  μˆ˜λŠ” μ—†μŠ΅λ‹ˆλ‹€. μˆ˜μ‹μ— ν¬ν•¨λœ μ—°μ‚°μžκ°€ 2개라면 μ •μ˜ν•  수 μžˆλŠ” μ—°μ‚°μž μš°μ„ μˆœμœ„ 쑰합은 2! = 2가지이며, μ—°μ‚°μžκ°€ 3개라면 3! = 6κ°€μ§€ 쑰합이 κ°€λŠ₯ν•©λ‹ˆλ‹€. λ§Œμ•½ κ³„μ‚°λœ κ²°κ³Όκ°€ 음수라면 ν•΄λ‹Ή 숫자의 μ ˆλŒ“κ°’μœΌλ‘œ λ³€ν™˜ν•˜μ—¬ μ œμΆœν•˜λ©° μ œμΆœν•œ μˆ«μžκ°€ κ°€μž₯ 큰 μ°Έκ°€μžλ₯Ό 우승자둜 μ„ μ •ν•˜λ©°, μš°μŠΉμžκ°€ μ œμΆœν•œ 숫자λ₯Ό μš°μŠΉμƒκΈˆμœΌλ‘œ μ§€κΈ‰ν•˜κ²Œ λ©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, μ°Έκ°€μž 쀑 λ„€μ˜€κ°€ μ•„λž˜μ™€ 같은 μˆ˜μ‹μ„ μ „λ‹¬λ°›μ•˜λ‹€κ³  κ°€μ •ν•©λ‹ˆλ‹€.

"100-200*300-500+20"

일반적으둜 μˆ˜ν•™ 및 μ „μ‚°ν•™μ—μ„œ μ•½μ†λœ μ—°μ‚°μž μš°μ„ μˆœμœ„μ— λ”°λ₯΄λ©΄ λ”ν•˜κΈ°μ™€ λΉΌκΈ°λŠ” μ„œλ‘œ λ™λ“±ν•˜λ©° κ³±ν•˜κΈ°λŠ” λ”ν•˜κΈ°, 빼기에 λΉ„ν•΄ μš°μ„ μˆœμœ„κ°€ λ†’μ•„ * > +,- 둜 μš°μ„ μˆœμœ„κ°€ μ •μ˜λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€. λŒ€νšŒ κ·œμΉ™μ— 따라 + > - > * λ˜λŠ” - > * > + λ“±κ³Ό 같이 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •μ˜ν•  수 μžˆμœΌλ‚˜ +,* > - λ˜λŠ” * > +,- 처럼 2개 μ΄μƒμ˜ μ—°μ‚°μžκ°€ λ™μΌν•œ μˆœμœ„λ₯Ό 가지도둝 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •μ˜ν•  μˆ˜λŠ” μ—†μŠ΅λ‹ˆλ‹€. μˆ˜μ‹μ— μ—°μ‚°μžκ°€ 3개 μ£Όμ–΄μ‘ŒμœΌλ―€λ‘œ κ°€λŠ₯ν•œ μ—°μ‚°μž μš°μ„ μˆœμœ„ 쑰합은 3! = 6가지이며, κ·Έ 쀑 + > - > * 둜 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •ν•œλ‹€λ©΄ 결괏값은 22,000원이 λ©λ‹ˆλ‹€. λ°˜λ©΄μ— * > + > - 둜 μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ •ν•œλ‹€λ©΄ μˆ˜μ‹μ˜ 결괏값은 -60,420 μ΄μ§€λ§Œ, κ·œμΉ™μ— 따라 우승 μ‹œ μƒκΈˆμ€ μ ˆλŒ“κ°’μΈ 60,420원이 λ©λ‹ˆλ‹€.

μ°Έκ°€μžμ—κ²Œ μ£Όμ–΄μ§„ μ—°μ‚° μˆ˜μ‹μ΄ λ‹΄κΈ΄ λ¬Έμžμ—΄ expression이 λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 우승 μ‹œ 받을 수 μžˆλŠ” κ°€μž₯ 큰 μƒκΈˆ κΈˆμ•‘μ„ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • expression은 길이가 3 이상 100 μ΄ν•˜μΈ λ¬Έμžμ—΄μž…λ‹ˆλ‹€.
  • expression은 곡백문자, κ΄„ν˜Έλ¬Έμž 없이 μ˜€λ‘œμ§€ μˆ«μžμ™€ 3κ°€μ§€μ˜ μ—°μ‚°μž(+, -, *) 만으둜 이루어진 μ˜¬λ°”λ₯Έ μ€‘μœ„ν‘œκΈ°λ²•(μ—°μ‚°μ˜ 두 λŒ€μƒ 사이에 μ—°μ‚°κΈ°ν˜Έλ₯Ό μ‚¬μš©ν•˜λŠ” 방식)으둜 ν‘œν˜„λœ μ—°μ‚°μ‹μž…λ‹ˆλ‹€. 잘λͺ»λœ 연산식은 μž…λ ₯으둜 μ£Όμ–΄μ§€μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

    • 즉, "402+-561*"처럼 잘λͺ»λœ μˆ˜μ‹μ€ μ˜¬λ°”λ₯Έ μ€‘μœ„ν‘œκΈ°λ²•μ΄ μ•„λ‹ˆλ―€λ‘œ μ£Όμ–΄μ§€μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
  • expression의 ν”Όμ—°μ‚°μž(operand)λŠ” 0 이상 999 μ΄ν•˜μ˜ μˆ«μžμž…λ‹ˆλ‹€.

    • 즉, "100-2145*458+12"처럼 999λ₯Ό μ΄ˆκ³Όν•˜λŠ” ν”Όμ—°μ‚°μžκ°€ ν¬ν•¨λœ μˆ˜μ‹μ€ μž…λ ₯으둜 μ£Όμ–΄μ§€μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
    • "-56+100"처럼 ν”Όμ—°μ‚°μžκ°€ 음수인 μˆ˜μ‹λ„ μž…λ ₯으둜 μ£Όμ–΄μ§€μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
  • expression은 적어도 1개 μ΄μƒμ˜ μ—°μ‚°μžλ₯Ό ν¬ν•¨ν•˜κ³  μžˆμŠ΅λ‹ˆλ‹€.
  • μ—°μ‚°μž μš°μ„ μˆœμœ„λ₯Ό μ–΄λ–»κ²Œ μ μš©ν•˜λ”λΌλ„, expression의 쀑간 계산값과 μ΅œμ’… 결괏값은 μ ˆλŒ“κ°’μ΄ 263 - 1 μ΄ν•˜κ°€ λ˜λ„λ‘ μž…λ ₯이 μ£Όμ–΄μ§‘λ‹ˆλ‹€.
  • 같은 μ—°μ‚°μžλΌλ¦¬λŠ” μ•žμ— μžˆλŠ” κ²ƒμ˜ μš°μ„ μˆœμœ„κ°€ 더 λ†’μŠ΅λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

expression return
"100-200*300-500+20" 60420
"50*6-3*2" 300

πŸ“ Logic

private void compute(int n) { ArrayList<Long> numbers = new ArrayList<>(nums); StringBuilder tmpOps = new StringBuilder(operands); for (char p : perm) { int idx = tmpOps.indexOf(String.valueOf(p)); while(idx != -1) { long n1 = numbers.get(idx); long n2 = numbers.get(idx+1); numbers.set(idx, calculator(n1,n2,p)); numbers.remove(idx+1); tmpOps.deleteCharAt(idx); idx = tmpOps.indexOf(String.valueOf(p)); } } long sum = Math.abs(numbers.get(0)); if (answer < sum) answer = sum; }
  • μˆ˜μ‹μ˜ μˆ«μžλ“€μ„ μ €μž₯ν•˜κ³  μžˆλŠ” nums 을 λ³΅μ‚¬ν•œ numbers 와 μ—°μ‚°μžλ“€μ„ μˆœμ„œλŒ€λ‘œ μ €μž₯ν•˜λŠ” operands λ₯Ό λ³΅μ‚¬ν•œ tmpOps λ₯Ό μ‚¬μš©ν•œλ‹€.

    • 이후 계산 μ‹œ μˆ«μžμ™€ μ—°μ‚°μžλ₯Ό λ°°μ—΄μ—μ„œ μ‚­μ œν•˜κΈ° μœ„ν•΄ μž„μ‹œ μ €μž₯μ†Œλ₯Ό μ‚¬μš©ν•œλ‹€.
  • μš°μ„  μˆœμœ„λŒ€λ‘œ μ—°μ‚°μžλ₯Ό μ €μž₯ν•œ perm 을 νƒμƒ‰ν•˜λ©΄μ„œ, ν•΄λ‹Ή μ—°μ‚°μžμ˜ μœ„μΉ˜λ₯Ό κΈ°μ€€μœΌλ‘œ μˆ«μžλ“€μ„ κ³„μ‚°ν•˜κ³ , λŒ€μΉ˜ν•œ ν›„, μ‚­μ œν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { long answer = 0; ArrayList<Long> nums = new ArrayList<>(); ArrayList<Character> perm = new ArrayList<>(); StringBuilder operands = new StringBuilder(); public long solution(String expression) { StringBuilder tmp = new StringBuilder(); for (int i = 0; i < expression.length(); i++) { char ch = expression.charAt(i); if (48 <= ch && ch <= 57) tmp.append(ch); else { nums.add((long) Integer.parseInt(String.valueOf(tmp))); if (!perm.contains(ch)) perm.add(ch); operands.append(ch); tmp.delete(0, tmp.length()); } } nums.add((long) Integer.parseInt(String.valueOf(tmp))); // μˆœμ—΄ 생성 makePerm(0, perm.size(), perm.size()); return answer; } private void makePerm(int depth, int n, int r) { if (depth == r) { compute(n); return; } for (int i = depth; i < n; i++) { Collections.swap(perm, depth, i); makePerm(depth + 1, n, r); Collections.swap(perm, depth, i); } } private void compute(int n) { ArrayList<Long> numbers = new ArrayList<>(nums); // μ—°μ‚°μž μž„μ‹œ 배열이 ν•„μš” // string은 각 λ¬Έμžλ³„ μœ„μΉ˜ μ‘°νšŒκ°€ κ°€λŠ₯ν•˜μ§€λ§Œ, μš”μ†Œ μ‚­μ œκ°€ μ•ˆλ¨ // arrayListλŠ” μš”μ†Œ μ‚­μ œκ°€ μš©μ΄ν•˜μ§€λ§Œ, μœ„μΉ˜ μ‘°νšŒκ°€ μ•ˆλ¨ StringBuilder tmpOps = new StringBuilder(operands); for (char p : perm) { int idx = tmpOps.indexOf(String.valueOf(p)); while(idx != -1) { long n1 = numbers.get(idx); long n2 = numbers.get(idx+1); numbers.set(idx, calculator(n1,n2,p)); numbers.remove(idx+1); tmpOps.deleteCharAt(idx); idx = tmpOps.indexOf(String.valueOf(p)); } } long sum = Math.abs(numbers.get(0)); if (answer < sum) answer = sum; } private long calculator(long n1, long n2, char op) { return switch (op) { case '-' -> n1 - n2; case '+' -> n1 + n2; case '*' -> n1 * n2; default -> 0; }; } }

✏️ Review

  • μ—°μ‚°μžμ— λŒ€ν•œ μˆœμ—΄μ΄ ν•„μš”ν•˜λ‹€λŠ” 점은 μ‰½κ²Œ μ•Œμ•˜μ§€λ§Œ, 이후 계산을 κ΅¬ν˜„ν•˜λŠ”λ° μ‹œκ°„μ„ λ„ˆλ¬΄ 많이 썼닀.
  • 아직 μžλ°”μ— λŒ€ν•œ 곡뢀가 더 ν•„μš”ν•  것 κ°™λ‹€. (String, StringBuilder, ArrayList<String> μ—μ„œ μ‚¬μš©ν•˜λŠ” λ©”μ†Œλ“œ)

πŸ“• 좜처

Programmers : https://programmers.co.kr/learn/courses/30/lessons/67257

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€